Data Structures & Algorithms (DSA)

━━━━━━━━━━━━━━━━━━━━━━
1. What is DSA?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

DSA stands for Data Structures and Algorithms.

• Data Structure is a way of organizing and storing data efficiently.
• Algorithm is a step-by-step procedure used to solve a problem.

Efficient DSA helps improve the speed and memory usage of programs.

━━━━━━━━━━━━━━━━━━━━━━
2. Why is DSA Important?
━━━━━━━━━━━━━━━━━━━━━━

DSA is important because it:

• Improves execution speed
• Uses memory efficiently
• Enhances problem-solving skills
• Helps build optimized applications
• Is essential for coding interviews

━━━━━━━━━━━━━━━━━━━━━━
3. Types of Data Structures
━━━━━━━━━━━━━━━━━━━━━━

1. Linear Data Structures

Elements are stored sequentially.

Examples:

• Array
• Linked List
• Stack
• Queue

━━━━━━━━━━━━━━━━━━━━━━

2. Non-Linear Data Structures

Elements are stored hierarchically.

Examples:

• Tree
• Graph
• Heap
• Trie

━━━━━━━━━━━━━━━━━━━━━━
4. What is an Array?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

An Array is a collection of elements stored in contiguous memory locations.

Example:

10 20 30 40 50

Advantages:

• Fast access using index
• Easy traversal

Disadvantages:

• Fixed size
• Costly insertion and deletion

Applications:

• Matrices
• Searching
• Sorting

━━━━━━━━━━━━━━━━━━━━━━
5. What is a Linked List?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Linked List is a collection of nodes connected using pointers.

Each node contains:

• Data
• Next Pointer

Example:

10 → 20 → 30 → NULL

Advantages:

• Dynamic size
• Easy insertion and deletion

Disadvantages:

• No direct indexing
• Extra memory for pointers

Types:

• Singly Linked List
• Doubly Linked List
• Circular Linked List

━━━━━━━━━━━━━━━━━━━━━━
Difference Between Array and Linked List
━━━━━━━━━━━━━━━━━━━━━━

Array

• Contiguous memory
• Fixed size
• Fast random access
• Slow insertion/deletion

Linked List

• Non-contiguous memory
• Dynamic size
• Sequential access
• Fast insertion/deletion

━━━━━━━━━━━━━━━━━━━━━━
6. What is a Stack?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Stack follows the LIFO (Last In, First Out) principle.

Example:

Stack of Plates

Operations:

• Push
• Pop
• Peek/Top
• isEmpty

Applications:

• Function Calls
• Undo Operation
• Browser History
• Expression Evaluation

━━━━━━━━━━━━━━━━━━━━━━
7. What is a Queue?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Queue follows the FIFO (First In, First Out) principle.

Example:

Queue at a Ticket Counter

Operations:

• Enqueue
• Dequeue
• Front
• Rear

Applications:

• CPU Scheduling
• Printer Queue
• Task Scheduling

━━━━━━━━━━━━━━━━━━━━━━
Difference Between Stack and Queue
━━━━━━━━━━━━━━━━━━━━━━

Stack

• LIFO
• Push/Pop
• One end

Queue

• FIFO
• Enqueue/Dequeue
• Two ends

━━━━━━━━━━━━━━━━━━━━━━
8. What is a Tree?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Tree is a hierarchical data structure consisting of nodes connected by edges.

Important Terms:

• Root
• Parent
• Child
• Leaf
• Height
• Depth

Applications:

• File System
• XML
• Organization Chart

━━━━━━━━━━━━━━━━━━━━━━
9. What is a Binary Tree?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Binary Tree is a tree where each node has at most two children.

• Left Child
• Right Child

━━━━━━━━━━━━━━━━━━━━━━
10. What is a Binary Search Tree (BST)?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Binary Search Tree (BST) is a Binary Tree where:

Left Child < Root < Right Child

Example:

        50
       /  \
     30    70
    / \    / \
   20 40 60 80

Advantages:

• Fast Searching
• Fast Insertion
• Fast Deletion

Average Time Complexity:

O(log n)


━━━━━━━━━━━━━━━━━━━━━━
11. What is a Graph?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Graph is a collection of:

• Vertices (Nodes)
• Edges (Connections)

Applications:

• Google Maps
• Social Networks
• Computer Networks

Types:

• Directed Graph
• Undirected Graph
• Weighted Graph
• Unweighted Graph

━━━━━━━━━━━━━━━━━━━━━━
12. What is Hashing?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Hashing is a technique that maps data to an index using a Hash Function.

It is used in:

• Hash Tables
• Dictionaries
• Maps

Advantages:

• Very Fast Searching
• Average Time Complexity: O(1)

Applications:

• Password Storage
• Database Indexing
• Caching

━━━━━━━━━━━━━━━━━━━━━━
13. What is a Heap?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

A Heap is a Complete Binary Tree.

Types:

Max Heap

• Parent > Children

Min Heap

• Parent < Children

Applications:

• Priority Queue
• CPU Scheduling
• Heap Sort

━━━━━━━━━━━━━━━━━━━━━━
14. What is a Trie?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Trie is a tree-like data structure used to store strings efficiently.

Applications:

• Auto Complete
• Spell Checker
• Dictionary Search

━━━━━━━━━━━━━━━━━━━━━━
15. Searching Algorithms
━━━━━━━━━━━━━━━━━━━━━━

Linear Search

Answer:

Checks every element one by one.

Time Complexity:

O(n)

━━━━━━━━━━━━━━━━━━━━━━

Binary Search

Answer:

Works only on sorted arrays.

Time Complexity:

O(log n)

━━━━━━━━━━━━━━━━━━━━━━
Difference Between Linear Search and Binary Search
━━━━━━━━━━━━━━━━━━━━━━

Linear Search

• Works on any array
• Sequential checking
• Time Complexity: O(n)

Binary Search

• Requires sorted array
• Divide and Conquer approach
• Time Complexity: O(log n)

━━━━━━━━━━━━━━━━━━━━━━
16. Sorting Algorithms
━━━━━━━━━━━━━━━━━━━━━━

Basic Sorting Algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort

Interview Question:

Which sorting algorithm is the fastest?

Answer:

• Quick Sort → Average O(n log n)
• Merge Sort → Guaranteed O(n log n)

━━━━━━━━━━━━━━━━━━━━━━
17. What is Recursion?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Recursion is a technique where a function calls itself to solve a problem.

Examples:

• Factorial
• Fibonacci
• Tree Traversal

Advantages:

• Cleaner Code
• Suitable for Tree Problems

Disadvantages:

• More Memory Usage
• Stack Overflow if not handled properly

━━━━━━━━━━━━━━━━━━━━━━
18. What is Time Complexity?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Time Complexity measures how the execution time of an algorithm grows as the input size increases.

Common Time Complexities:

• O(1) → Constant Time
• O(log n) → Logarithmic
• O(n) → Linear
• O(n log n) → Linearithmic
• O(n²) → Quadratic
• O(2ⁿ) → Exponential

━━━━━━━━━━━━━━━━━━━━━━
19. What is Space Complexity?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Space Complexity measures the amount of memory required by an algorithm during execution.

Lower space complexity is generally preferred because it uses less memory.

━━━━━━━━━━━━━━━━━━━━━━
20. What is Big O Notation?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Big O Notation represents the worst-case performance of an algorithm.

Examples:

• Array Access → O(1)
• Linear Search → O(n)
• Binary Search → O(log n)
• Bubble Sort → O(n²)
• Merge Sort → O(n log n)


━━━━━━━━━━━━━━━━━━━━━━
21. What are Asymptotic Notations?
━━━━━━━━━━━━━━━━━━━━━━

Answer:

Asymptotic Notations are used to measure the performance of an algorithm.

Types:

• Big O (O) → Worst Case
• Omega (Ω) → Best Case
• Theta (Θ) → Average/Exact Case

━━━━━━━━━━━━━━━━━━━━━━
22. Common Time Complexities
━━━━━━━━━━━━━━━━━━━━━━

O(1)

• Constant Time
• Example: Array Access

━━━━━━━━━━━━━━━━━━━━━━

O(log n)

• Logarithmic Time
• Example: Binary Search

━━━━━━━━━━━━━━━━━━━━━━

O(n)

• Linear Time
• Example: Linear Search

━━━━━━━━━━━━━━━━━━━━━━

O(n log n)

• Linearithmic Time
• Example: Merge Sort

━━━━━━━━━━━━━━━━━━━━━━

O(n²)

• Quadratic Time
• Example: Bubble Sort

━━━━━━━━━━━━━━━━━━━━━━

O(2ⁿ)

• Exponential Time
• Example: Recursive Fibonacci

━━━━━━━━━━━━━━━━━━━━━━

O(n!)

• Factorial Time
• Example: Traveling Salesman (Brute Force)

━━━━━━━━━━━━━━━━━━━━━━
23. Difference Between Tree and Graph
━━━━━━━━━━━━━━━━━━━━━━

Tree

• No cycles
• One root node
• Always connected

Graph

• May contain cycles
• No fixed root
• May or may not be connected

━━━━━━━━━━━━━━━━━━━━━━
24. Difference Between BFS and DFS
━━━━━━━━━━━━━━━━━━━━━━

BFS (Breadth First Search)

• Explores level by level
• Uses Queue
• Finds shortest path in unweighted graphs

Applications:

• Shortest Path
• Network Broadcasting

━━━━━━━━━━━━━━━━━━━━━━

DFS (Depth First Search)

• Goes as deep as possible before backtracking
• Uses Stack or Recursion

Applications:

• Cycle Detection
• Topological Sorting

━━━━━━━━━━━━━━━━━━━━━━
25. Common Operations & Time Complexities
━━━━━━━━━━━━━━━━━━━━━━

Array

• Search → O(n)
• Insert → O(n)
• Delete → O(n)

━━━━━━━━━━━━━━━━━━━━━━

Linked List

• Search → O(n)
• Insert → O(1)*
• Delete → O(1)*

*At a known position or head.

━━━━━━━━━━━━━━━━━━━━━━

Stack

• Search → O(n)
• Push → O(1)
• Pop → O(1)

━━━━━━━━━━━━━━━━━━━━━━

Queue

• Search → O(n)
• Enqueue → O(1)
• Dequeue → O(1)

━━━━━━━━━━━━━━━━━━━━━━

Binary Search Tree (Average)

• Search → O(log n)
• Insert → O(log n)
• Delete → O(log n)

━━━━━━━━━━━━━━━━━━━━━━

Hash Table (Average)

• Search → O(1)
• Insert → O(1)
• Delete → O(1)

━━━━━━━━━━━━━━━━━━━━━━
26. Advantages of DSA
━━━━━━━━━━━━━━━━━━━━━━

• Efficient Memory Usage
• Faster Execution
• Better Optimization
• Easier Problem Solving
• Scalable Applications
• Better Coding Skills
• Improves Logical Thinking



━━━━━━━━━━━━━━━━━━━━━━
Most Frequently Asked DSA Interview Questions
━━━━━━━━━━━━━━━━━━━━━━

1. What is DSA?

2. Difference Between Data Structure and Algorithm.

3. What is an Array?

4. Difference Between Array and Linked List.

5. What is a Stack?

6. What is a Queue?

7. Difference Between Stack and Queue.

8. What is a Tree?

9. What is a Binary Tree?

10. What is a Binary Search Tree (BST)?

11. What is a Graph?

12. What is Hashing?

13. What is a Heap?

14. What is a Trie?

15. Difference Between Linear Search and Binary Search.

16. What is Recursion?

17. What is Time Complexity?

18. What is Space Complexity?

19. What is Big O Notation?

20. Difference Between BFS and DFS.

21. Difference Between Tree and Graph.

22. Explain O(1), O(log n), O(n), O(n log n), and O(n²).

23. Name Some Sorting Algorithms.

24. Which Data Structure is Used for Function Calls?

Answer:

Stack

25. Which Data Structure is Used for CPU Scheduling?

Answer:

Queue

━━━━━━━━━━━━━━━━━━━━━━
Quick Revision
━━━━━━━━━━━━━━━━━━━━━━

✔ DSA → Data Structures and Algorithms

✔ Data Structure → Organizes data efficiently.

✔ Algorithm → Step-by-step solution to a problem.

✔ Array → Contiguous memory, fast indexing.

✔ Linked List → Nodes connected using pointers.

✔ Stack → LIFO (Last In, First Out).

✔ Queue → FIFO (First In, First Out).

✔ Tree → Hierarchical data structure.

✔ Binary Tree → Maximum two children per node.

✔ BST → Left < Root < Right.

✔ Graph → Vertices connected by edges.

✔ Hashing → Fast lookup using hash functions.

✔ Heap → Complete binary tree used in priority queues.

✔ Trie → Tree for storing strings efficiently.

✔ Linear Search → O(n)

✔ Binary Search → O(log n), requires sorted array.

✔ Bubble Sort → O(n²)

✔ Merge Sort → O(n log n)

✔ Quick Sort → Average O(n log n)

✔ Recursion → Function calls itself.

✔ Time Complexity → Measures execution time growth.

✔ Space Complexity → Measures memory usage.

✔ Big O → Worst-case complexity.

✔ BFS → Queue, level-by-level traversal.

✔ DFS → Stack/Recursion, depth-first traversal.